class Solution(object):
    def minimizeTheDifference(self, mat, target):
        st = [0] * target
        m = len(mat)
        n = len(mat[0])
        min_num = [min(mat[i]) for i in range(m)]
        min_sum = sum(min_num)
        min_val = float('inf')
        for i in range(1, m):
            min_num[i] += min_num[i - 1]
        if min_sum >= target:
            return min_sum - target
        for j in range(n):
            if mat[0][j] < target:
                st[mat[0][j] - 1] = 1
            else:
                if mat[0][j] >= target:
                    min_val = min(min_val, mat[0][j] + min_num[-1] - min_num[0] - target)
        for i in range(1, m):
            next_st = [0] * target
            for k in range(target):
                if st[k]:
                    for j in range(n):
                        if k + 1 + mat[i][j] < target:
                            next_st[k + mat[i][j]] = 1
                        else:
                            if k + 1 + mat[i][j] >= target:
                                min_val = min(min_val, k + 1 + mat[i][j] + min_num[-1] - min_num[i] - target)
            st = next_st
        for i in range(target - 1, - 1, -1):
            if st[i]:
                return min(target - i - 1, min_val)


data = Solution()
mat = [
    [70, 1, 1, 1, 70, 1, 70, 70, 70, 3, 1, 1, 1, 1, 70, 70, 1, 70, 1, 70, 70, 70, 70, 1, 70, 70, 1, 70, 1, 1, 70, 1, 70,
     1, 70, 70, 70],
    [1, 1, 1, 70, 1, 70, 70, 1, 70, 70, 70, 70, 1, 70, 70, 70, 70, 1, 70, 1, 70, 1, 70, 1, 1, 1, 3, 1, 1, 70, 1, 1, 70,
     70, 70, 1, 70],
    [70, 1, 1, 1, 70, 70, 70, 1, 1, 3, 1, 1, 1, 70, 1, 1, 70, 1, 1, 70, 1, 70, 70, 70, 1, 1, 1, 70, 70, 70, 1, 70, 70,
     70, 1, 1, 70],
    [70, 1, 1, 70, 70, 70, 1, 1, 1, 1, 70, 1, 70, 70, 1, 70, 1, 70, 3, 1, 70, 70, 1, 1, 70, 70, 70, 1, 1, 70, 70, 1, 70,
     70, 1, 70, 1],
    [1, 1, 70, 1, 70, 1, 1, 70, 70, 1, 70, 70, 70, 1, 70, 1, 70, 1, 1, 70, 70, 1, 1, 70, 1, 1, 1, 70, 70, 1, 70, 1, 1,
     3, 70, 70, 70],
    [70, 70, 70, 70, 1, 1, 1, 70, 70, 1, 70, 70, 1, 70, 70, 1, 1, 1, 70, 1, 70, 70, 1, 70, 70, 70, 70, 1, 1, 70, 70, 70,
     1, 70, 3, 70, 70],
    [1, 1, 70, 1, 1, 70, 1, 1, 70, 1, 1, 70, 70, 1, 70, 1, 1, 70, 1, 1, 70, 1, 70, 70, 1, 1, 1, 1, 3, 70, 70, 1, 1, 70,
     70, 70, 1],
    [1, 70, 1, 1, 70, 70, 70, 70, 1, 70, 1, 70, 1, 70, 70, 1, 1, 1, 70, 70, 70, 1, 1, 70, 1, 70, 1, 70, 1, 1, 70, 70,
     70, 1, 3, 1, 70],
    [1, 1, 1, 1, 1, 1, 70, 70, 1, 1, 1, 1, 1, 70, 70, 1, 70, 70, 70, 1, 70, 1, 1, 1, 70, 1, 1, 70, 1, 70, 70, 70, 3, 1,
     70, 70, 1],
    [1, 1, 70, 1, 70, 70, 3, 1, 70, 70, 1, 1, 70, 1, 1, 1, 1, 70, 70, 70, 1, 70, 70, 70, 1, 70, 70, 1, 1, 1, 70, 70, 1,
     1, 70, 1, 1],
    [70, 70, 70, 1, 1, 1, 70, 1, 70, 70, 1, 70, 70, 70, 1, 1, 1, 1, 1, 1, 1, 1, 70, 70, 1, 1, 70, 1, 1, 3, 70, 70, 1,
     70, 70, 1, 1],
    [1, 1, 70, 1, 1, 70, 1, 70, 3, 70, 1, 1, 1, 1, 70, 1, 70, 1, 70, 70, 70, 70, 70, 1, 1, 1, 1, 70, 70, 70, 1, 70, 70,
     70, 1, 70, 1],
    [70, 70, 70, 1, 70, 1, 1, 1, 70, 70, 1, 70, 70, 1, 1, 70, 1, 3, 70, 1, 70, 1, 70, 1, 1, 70, 1, 70, 1, 1, 1, 70, 1,
     1, 70, 1, 1],
    [70, 1, 70, 1, 1, 70, 70, 70, 70, 70, 70, 70, 1, 70, 1, 1, 1, 70, 1, 1, 70, 70, 70, 70, 1, 1, 70, 70, 70, 3, 70, 70,
     1, 70, 70, 70, 1],
    [70, 1, 70, 1, 3, 70, 70, 70, 70, 70, 1, 70, 1, 1, 1, 1, 1, 1, 1, 1, 70, 70, 70, 70, 70, 70, 1, 70, 1, 70, 70, 1,
     70, 1, 70, 1, 1],
    [1, 1, 70, 1, 1, 70, 1, 1, 3, 1, 1, 1, 1, 1, 70, 1, 70, 70, 1, 70, 1, 70, 1, 1, 1, 70, 1, 70, 70, 70, 70, 70, 1, 70,
     1, 1, 1],
    [3, 1, 1, 70, 70, 70, 1, 1, 70, 70, 70, 70, 1, 1, 70, 1, 70, 1, 70, 70, 70, 1, 70, 1, 70, 1, 1, 70, 70, 70, 70, 70,
     70, 70, 1, 1, 70],
    [70, 1, 70, 1, 70, 1, 1, 1, 1, 1, 1, 1, 70, 70, 70, 70, 1, 1, 70, 1, 70, 70, 1, 70, 70, 70, 1, 70, 1, 1, 1, 1, 1,
     70, 3, 70, 70],
    [1, 3, 70, 1, 70, 70, 1, 70, 1, 70, 1, 1, 1, 1, 1, 70, 70, 70, 70, 70, 1, 1, 70, 70, 70, 1, 70, 70, 70, 70, 70, 70,
     70, 1, 1, 70, 70],
    [70, 1, 1, 1, 1, 70, 1, 70, 70, 1, 3, 1, 1, 1, 70, 1, 1, 1, 1, 1, 1, 1, 70, 1, 1, 70, 70, 70, 1, 70, 1, 1, 70, 70,
     1, 1, 1],
    [70, 70, 1, 1, 70, 1, 70, 70, 70, 70, 70, 70, 70, 70, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 70, 70, 1, 1, 1, 1, 70, 1, 1,
     70, 70, 70],
    [1, 1, 70, 70, 70, 70, 70, 1, 1, 1, 70, 1, 3, 70, 70, 70, 1, 1, 70, 1, 1, 1, 1, 70, 70, 70, 70, 70, 70, 1, 70, 1, 1,
     1, 1, 70, 1],
    [1, 1, 70, 70, 1, 1, 3, 1, 1, 1, 70, 1, 1, 1, 70, 70, 70, 1, 70, 70, 1, 70, 70, 1, 1, 70, 1, 70, 1, 70, 1, 1, 1, 70,
     70, 70, 1],
    [1, 1, 1, 1, 70, 70, 1, 70, 1, 70, 1, 70, 70, 1, 70, 70, 1, 1, 70, 1, 70, 1, 1, 1, 1, 70, 70, 70, 70, 1, 70, 3, 70,
     70, 70, 1, 70],
    [1, 1, 70, 1, 1, 1, 70, 1, 1, 70, 1, 1, 70, 1, 1, 70, 1, 1, 1, 1, 70, 1, 1, 1, 3, 1, 70, 70, 70, 1, 70, 70, 1, 1, 1,
     70, 1],
    [1, 1, 1, 70, 1, 1, 1, 70, 70, 70, 1, 1, 70, 70, 1, 70, 70, 1, 1, 1, 70, 70, 70, 1, 1, 70, 70, 70, 1, 1, 70, 1, 70,
     1, 70, 1, 3],
    [70, 1, 1, 1, 70, 1, 1, 1, 1, 1, 70, 1, 70, 1, 1, 1, 70, 1, 70, 1, 3, 1, 1, 70, 1, 1, 1, 1, 70, 70, 1, 1, 70, 70,
     70, 1, 1],
    [70, 1, 1, 1, 1, 70, 70, 70, 1, 70, 1, 1, 1, 1, 1, 1, 70, 1, 3, 70, 1, 1, 70, 70, 70, 70, 1, 1, 1, 70, 1, 1, 70, 1,
     70, 70, 70],
    [70, 70, 1, 1, 1, 1, 1, 1, 70, 1, 70, 1, 1, 1, 70, 70, 70, 70, 1, 1, 1, 1, 1, 1, 70, 1, 1, 70, 1, 1, 70, 70, 70, 1,
     70, 3, 70],
    [1, 70, 1, 1, 70, 70, 1, 70, 1, 70, 70, 1, 70, 1, 1, 1, 3, 70, 70, 70, 70, 70, 70, 1, 1, 1, 70, 1, 70, 1, 70, 1, 70,
     1, 70, 1, 1],
    [70, 1, 70, 70, 1, 1, 70, 70, 1, 1, 70, 70, 1, 1, 70, 1, 1, 70, 1, 70, 1, 1, 70, 1, 1, 1, 70, 70, 1, 70, 1, 70, 1,
     70, 1, 70, 3],
    [70, 1, 70, 1, 1, 70, 1, 1, 1, 1, 1, 1, 70, 70, 1, 70, 70, 70, 70, 70, 3, 1, 1, 70, 70, 70, 1, 1, 70, 1, 1, 1, 1,
     70, 1, 1, 70],
    [1, 70, 70, 70, 1, 70, 1, 70, 1, 1, 70, 1, 70, 1, 70, 1, 1, 1, 1, 1, 1, 1, 1, 70, 70, 1, 70, 1, 70, 70, 1, 1, 70,
     70, 3, 70, 70],
    [70, 3, 70, 70, 1, 1, 1, 70, 1, 1, 70, 70, 1, 1, 1, 70, 70, 70, 1, 1, 70, 1, 1, 70, 1, 70, 70, 1, 1, 1, 70, 1, 70,
     1, 1, 1, 70],
    [70, 70, 1, 1, 1, 70, 1, 70, 1, 1, 70, 70, 1, 70, 70, 70, 1, 70, 1, 70, 1, 70, 1, 70, 1, 70, 70, 1, 1, 70, 1, 70, 1,
     1, 1, 3, 70],
    [70, 1, 70, 1, 1, 70, 1, 1, 1, 1, 1, 1, 70, 70, 1, 1, 70, 70, 1, 70, 70, 1, 70, 70, 1, 1, 70, 1, 1, 3, 70, 70, 70,
     1, 1, 70, 1],
    [1, 70, 1, 1, 1, 70, 1, 1, 70, 1, 70, 70, 70, 1, 1, 70, 1, 1, 3, 1, 70, 1, 70, 70, 1, 1, 1, 1, 1, 1, 70, 1, 1, 1, 1,
     70, 1]]
target = 113
print(data.minimizeTheDifference(mat, target))
